//#include <iostream>
//#include <cstring>
//using namespace std;
//
//
//int n, V;
//const int N = 1010;
//int v[N], w[N];
//int dp[N];
//
//int main()
//{
//    cin >> n >> V;
//    for (int i = 1; i <= n; i++)
//        cin >> v[i] >> w[i];
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = V; j >= v[i]; j--)
//        {
//            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
//        }
//    }
//    std::cout << dp[V] << std::endl;
//
//    memset(dp, 0, sizeof(dp));
//    for (int i = 1; i <= V; i++)
//        dp[i] = -1;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = V; j >= v[i]; j--)
//        {
//            if (dp[j - v[i]] != -1)
//                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
//        }
//    }
//    std::cout << (dp[V] == -1 ? 0 : dp[V]) << std::endl;
//    return 0;
//}





#include <iostream>
#include <cstring>
using namespace std;

int n, V;
int v[1010] = { 0 }, w[1010] = { 0 };
int dp[1001] = { 0 };
int main()
{
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // dp[i][j] = max(dp[i- 1][j], d[i- 1][j - x], dp[i - 1][j - 2x] ... )
    // dp[i][j] = max(dp[i][j - x], dp[i - 1][j])
    // ques1
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= V; j++)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[V] << endl;

    /// ques2
    //  dp[i][j] = max(dp[i][j - x], dp[i - 1][j])
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= V; i++)
        dp[i] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = v[i]; j <= V; j++)
            if (dp[j - v[i]] != -1)
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << ((dp[V] == -1) ? 0 : dp[V]) << endl;
    return 0;
}